package edu.usc.csci578.project;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

import edu.usc.csci578.project.generated.graph.ClusterEdge;
import edu.usc.csci578.project.util.parse.ArchGraphParser;
import edu.usc.csci578.project.util.parse.XMLJaxbParser;

/**
 * Detector for Brick Dependency Cycles
 */
public class BrickDependencyCycleDetector
{
	/**
	 * Default location of the smellArchGraph XML file
	 */
	private static final String DEFAULT_ARCH_GRAPH_XML = XMLJaxbParser.XML_HOME
			+ "oodt-filemgr_smellArchGraph.xml";

	/**
	 * Runs the BrickDependencyCycleDetector on the default XML file
	 * 
	 * @param args
	 *            optional:
	 *            <ul>
	 *            <li>First parameter: path to smellArchGraph XML file</li>
	 *            </ul>
	 * @throws IOException
	 *             on error writing cycles to the output file
	 * @throws FileNotFoundException
	 *             if the smellArchGraph XML file is not found
	 */
	public static void main(final String[] args) throws IOException,
			FileNotFoundException
	{
		BrickDependencyCycleDetector detector;
		if (args != null && args.length > 0)
			detector = new BrickDependencyCycleDetector(args[0]);
		else
			detector = new BrickDependencyCycleDetector();
		final List<List<String>> cycleList = detector
				.getBrickDependencyCycles();
		outputBrickDependencyCycles(new PrintWriter(System.out, true),
				cycleList);
		System.out.println("---");
		System.out.println(cycleList.size() + " brick dependency cycles found");
		int max = 0;
		for (final List<String> cycle : cycleList)
		{
			final int size = cycle.size();
			if (size > max)
				max = size;
		}
		System.out.println("Max cycle path length: " + max);
		System.out.println("---");
	}

	/**
	 * Outputs a list of brick dependency cycles to the specified PrintWriter
	 * 
	 * @param out
	 *            PrintWriter to output to
	 * @param cycleList
	 *            list of cycles to print
	 */
	public static void outputBrickDependencyCycles(final PrintWriter out,
			final List<List<String>> cycleList)
	{
		for (final List<String> cycle : cycleList)
		{
			out.println("Cycle START");
			for (final String s : cycle)
				out.println(s);
			out.println("Cycle END");
			out.println();
		}
	}

	/**
	 * All edges between bricks without any self-referential loops
	 */
	private final List<ClusterEdge> allEdges;
	/**
	 * Edges visited in the current Depth First Search
	 */
	private final Map<ClusterEdge, Boolean> currEdges = new HashMap<ClusterEdge, Boolean>();
	/**
	 * Output list of cycles found by the detector
	 */
	private final ArrayList<List<String>> cycleList = new ArrayList<List<String>>();
	/**
	 * List of all bricks that are 'sources' for an edge between bricks
	 */
	private final Set<String> srcBricks = new TreeSet<String>();

	/**
	 * Constructor for reading from the default smellArchGraph XML file
	 * 
	 * @throws FileNotFoundException
	 *             if the smellArchGraph XML file is not found
	 */
	public BrickDependencyCycleDetector() throws FileNotFoundException
	{
		this(DEFAULT_ARCH_GRAPH_XML);
	}

	/**
	 * Constructor for reading from a given smellArchGraph XML file
	 * 
	 * @param xmlFilePath
	 *            path to the smellArchGraph XML file
	 * @throws FileNotFoundException
	 *             if the smellArchGraph XML file is not found
	 */
	public BrickDependencyCycleDetector(final String xmlFilePath)
			throws FileNotFoundException
	{
		final ArchGraphParser parser = new ArchGraphParser(xmlFilePath);
		// Set global to JAXB extracted element
		allEdges = parser.getRootObject().getClusterEdge();
		// Holds the index of the edges to remove
		final List<ClusterEdge> removeList = new ArrayList<ClusterEdge>();
		// Loop through edges to find self-dependents, add to cycle list and tag
		// for removal
		for (final ClusterEdge edge : allEdges)
		{
			final String src = edge.getSrc();
			final String tgt = edge.getTgt();
			if (src.equals(tgt))
			{
				removeList.add(edge);
				final Stack<String> cycle = new Stack<String>();
				cycle.push(src);
				cycle.push(tgt);
				cycleList.add(cycle);
			}
		}
		// Loop through removal list and remove edges
		for (final ClusterEdge clusterEdge : removeList)
			allEdges.remove(clusterEdge);
	}

	/**
	 * Verifies if cycle is unique, and adds it to list accordingly.
	 * 
	 * @param child
	 *            last brick in the cycle
	 * @param currStack
	 *            stack of bricks representing path of the cycle
	 */
	private void addCycle(final String child, final Stack<String> currStack)
	{
		final List<String> cycle = extractCycle(child, currStack);
		if (!cycleList.contains(cycle))
			cycleList.add(cycle);
	}

	/**
	 * Use Depth-First Search Algorithm to traverse the dependency tree to find
	 * cycles.
	 * 
	 * @param rootBrick
	 *            the root of the Depth-First Search
	 */
	public void dfs(final String rootBrick)
	{
		// Sets all edges to unvisited
		currEdges.clear();
		for (final ClusterEdge edge : allEdges)
			currEdges.put(edge, false);
		final Stack<String> currStack = new Stack<String>();
		currStack.push(rootBrick);
		while (!currStack.isEmpty())
		{
			final String current = currStack.peek();
			final String child = getUnvisitedConnected(current);
			if (child != null)
			{
				if (child.equals(rootBrick))
				{
					addCycle(child, currStack); // Verifies uniqueness of cycle,
												// and adds to list, if
												// necessary
					currStack.push(child);
					currStack.pop();
				}
				else if (!currStack.contains(child))
					currStack.push(child);
			}
			else
				currStack.pop();
		}
	}

	/**
	 * Iterates through the stack and extracts the cycle
	 * 
	 * @param str
	 *            name of the last brick in the cycle
	 * @param s
	 *            stack of bricks representing the path of the cycle
	 * @return the cyclic path through a number of bricks; starts and ends with
	 *         the same brick
	 */
	private List<String> extractCycle(final String str, final Stack<String> s)
	{
		final List<String> cycle = new ArrayList<String>();
		String currBrick;
		for (int i = 0; i < s.size(); i++)
		{
			currBrick = s.get(i);
			cycle.add(currBrick);
		}
		cycle.add(str);
		return cycle;
	}

	/**
	 * Start method to initiate the algorithm
	 * 
	 * @return the list of cycles found
	 * 
	 * @throws IOException
	 *             on error writing cycles to the output file
	 */
	public List<List<String>> getBrickDependencyCycles() throws IOException
	{
		// Iterates through the allEdges method, adding all blocks that are
		// listed as sources for any edge
		srcBricks.clear();
		for (final ClusterEdge clusterEdge : allEdges)
		{
			final String brick = clusterEdge.getSrc();
			srcBricks.add(brick);
		}
		// Loop through the list of all source bricks (ClusterEdge.src) to
		// ensure no cycles are missed
		for (final String brick : srcBricks)
			dfs(brick);
		return cycleList;
	}

	/**
	 * Loops through edges not traversed during current DFS
	 * 
	 * @param current
	 *            current brick
	 * @return next unvisited brick that is the target of the current brick
	 */
	private String getUnvisitedConnected(final String current)
	{
		for (final ClusterEdge edge : currEdges.keySet())
			// If edge has not been tagged, and current brick
			// equals the edge source, return the target brick
			if (!currEdges.get(edge) && current.equals(edge.getSrc()))
			{
				currEdges.put(edge, true);
				return edge.getTgt();
			}
		return null;
	}
}
